#include <iostream>
#include "heapUtilities.h"

using namespace std;

void swap(int *array, int pos1, int pos2) {
	int temp;
	temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;
	
	return;
}

bool createHeap(int *array, unsigned int n) {
	int end = 1;
	int parent, child;
	for (end = 1; end < n; end++) {
		child = end;
		parent = (child - 1) / 2;
		while (parent >= 0 && parent < child) {
			if (array[parent] < array[child]) {
				swap(array, parent, child);
			}
			child = parent;
			parent = (child - 1) / 2;
		}
	}

	return true;
}

bool createHeap1(int *array, unsigned int n) {
	int index = (n - 1) / 2;
	int parent, child, swap_loc;
	while (index >= 0) {
		parent = index;
		child = 2 * parent + 1;
		while (child < n) {
			swap_loc = -1;
			if (array[parent] < array[child]) {
				swap_loc = child;
			}

			if (child + 1 < n) {
				if (array[parent] < array[child + 1] &&
					array[child] < array[child + 1]) {
					swap_loc = child + 1;
				}
			}

			if (swap_loc != -1) {
				swap(array, parent, swap_loc);
				parent = swap_loc;
				child = 2 * parent + 1;
			}
			else {
				break;
			}
		}
		--index;
	}
	
	return true;
}	

bool heapSort(int *array, unsigned int n) {
	// create a heap with root be the max
	//createHeap1(array, n);

	//start the heap sort
	int end = n - 1;
	int parent;

	while (end > 0) {
		swap(array, 0, end);
		parent = 0;
		int child = 2 * parent + 1;
		while (child < end) {
			int swap_loc = -1;
			if (array[parent] < array[child]) {
				swap_loc = child;
			}

			if (child + 1 < end) {
				if (array[parent] < array[child + 1] && 
    				array[child] < array[child + 1]) {
					swap_loc = child + 1;
				}
			}

			if (swap_loc != -1) {
				swap(array, parent, swap_loc);
				parent = swap_loc;
				child = 2 * parent + 1;
			}
			else {
				break;
			}
		}
		end -= 1;
	}

	return true;
}

